1. Field of the Invention
The present invention relates to the art of motion-compensated interframe coding applicable to the coding of moving images, and more particularly to a method of detecting similarity of small regions (blocks) in an image between frames.
The present invention is also concerned with an iterative transform coding process which is applicable to the coding of still images or moving images, and more particularly to a method of detecting similarity of small regions (blocks) in an image within a frame or between frames.
2. Description of the Prior Art
Moving image data have heretofore been compressed by the MPEG (Moving Picture Experts Group) interframe coding process which codes a frame by referring to other frames which precede and follow the frame in time, or the H.261 and H.263 coding processes which code a frame by referring to another frame which precedes the frame in time.
These interframe coding processes incorporate motion-compensated interframe coding principles by which a frame is coded while compensating for a motion produced between frames.
At present, different MPEG versions such as MPEG-1(ISO/IEC 11172) and MPEG-2(ISO/IEC 13818) are available in the art. Both MPEG-1 and MPEG-2 use three types of coded pictures including I-picture, P-picture, and B-picture. Specifically, a sequence of frames of a moving image is mixed with frames that have been coded with an either one of these types of coded pictures.
An I-picture is a picture frame that is intra-coded (intraframe-coded) independently of other frames. Macroblocks (a predetermined number of blocks of pixels) in the frame are all intra-coded. I-pictures which are periodically included in a sequence of frames of a moving image can be used as points for random access or error recovery.
A P-picture is a picture frame which is interframe predictive-coded from another frame that precedes the frame in time. The picture frame is predictive-coded only in a forward direction based on an I-picture or a P-picture positioned in the past.
A B-picture is a picture frame which is interframe predictive-coded from other two frames that precede and follow the picture frame in time. The picture frame is predictive-coded in a forward direction or a backward direction or both directions based on I-pictures or P-pictures that precede and follow the picture frame in time. The predictive direction is determined in terms of macroblocks.
ITU-T Recommendation H.261 and H.263 coding processes are the video coding standards for teleconferencing applications. The H.261 and H.263 coding processes do not compress a picture frame according to predictive-coding based on a frame that follows the picture frame in time, but compress a picture frame according to interframe predictive-coding based on a frame that precedes the picture frame in time. Specifically, the H.261 and H.263 coding processes use two types of coded pictures, i.e., I-picture and P-picture, and mix frames coded with either of these picture types with a sequence of frames of a moving image.
According to the above motion-compensated interframe coding principles, it is necessary to detect a motion vector in a moving image. One of processes for detecting such a motion vector is a block matching process.
The block matching process divides an image frame into rectangular regions (rectangular blocks) each comprising a matrix of 8.times.8 pixels or 16.times.16 pixels, and detects a motion per block between frames.
More specifically, the block matching process determines a motion vector by evaluating similarity between a block (input block) in a frame which it to be coded and blocks that are shifted a predetermined distance within a given search range about a block within a preceding frame (reference image frame) which is in the same position as the input block, and identifying a block (similar block) which has the highest similarity to the input block. For example, if a horizontal search range is .+-.15 pixels for each frame, then when a P-picture frame to be coded is 4 frames apart from a reference image frame, a search range of .+-.60 pixels is searched.
Therefore, a motion vector can be determined when similarity (predicted error) is calculated between blocks in an image frame to be coded and a reference image frame. As well known in the art, an accumulative sum of absolute errors AE or square errors SE is used as an evaluating function to determine similarity. An accumulative sum of absolute errors AE and an accumulative sum of square errors SE are expressed by the following equations: ##EQU1##
where x.sub.i : a pixel value in an input block or a range block;
X.sub.i : a pixel value in a search block or a domain block; PA1 N: the number of pixels in a block.
and
The coding of an image according to a conventional block matching process which uses square errors SE will be described below with reference to FIG. 1 of the accompanying drawings.
As shown in FIG. 1, a variable MIN which holds a minimum square error SE (block similarity is higher as the square error SE is smaller) is initialized in a step S60, and thereafter a first input block is read from an image frame to be coded in a step S61. Then, a first search block is read from a search range in a reference image frame in a step S62.
A square error SE between the input block and the search block is calculated in a step S63, and the calculated square error SE is compared with the variable MIN in a step S64. If the square error SE is smaller than the variable MIN, then the calculated square error SE is held as the variable MIN, and the position of the search block in the frame is held in a step S65.
The steps S62-S65 are repeated until it is decided that all search blocks in the search range are processed in a step S66. A square error SE smaller than the variable MIN held in the preceding processing cycle is determined and held, and the position of the search block the frame is held in the step S65. In this manner, the position of the search block whose similarity is highest in the search range (with the minimum square error SE) is identified.
A motion vector between the input block and the identified block whose similarity is highest is coded in a step S67.
The steps S61-S67 are repeated until it is decided that all input blocks in the frame to be coded are processed in a step S68, thereby coding motion vectors between the input blocks and the search block.
As a result, a search block whose similarity to each of all the input blocks in the frame to be coded is high is identified as a similar block, and a motion vector between the input block and the similar block is coded.
Another known block matching process is an iterative coding process (fractal coding process) which divides a still image or a moving image into a plurality of blocks, searches a search range established in the image for a block (domain block) similar to a block (range block) to be coded, and codes an affine transformation parameter between the range block and the domain block.
The iterative coding process models an image using its self-correlation and codes an affine transformation parameter representative of a feature of the image, as disclosed in "Fractal Image Compression" written by A. E. Barnsley and L. P. Hurd, Numerical Science series--4, published by Toppan, "Image compression by iterative coding" written by Ida and Datake, Communication society, Spring National Conference, D-341, 1991, "A novel fractal block-coding technique for digital images" written by A. E. Jacquin, ICASSP 90 Proceeding, M8. 2, 1992, and U.S. Pat. No. 5,065,447.
The coding of an image according to a conventional iterative coding process which uses square errors SE will be described below with reference to FIG. 2 of the accompanying drawings.
As shown in FIG. 2, a variable MIN which holds a minimum square error SE is initialized in a step S70, and thereafter a first range block is read from an image to be coded in a step S71. Then, the range block is affine-transformed with respect to a first domain block in a predetermined search range in a step S72, after which the first domain block is read in a step S73.
A square error SE between the range block and the domain block is calculated in a step S74, and the calculated square error SE is compared with the variable MIN in a step S75. If the square error SE is smaller than the variable MIN, then the calculated square error SE is held as the variable MIN, and the parameter of the affine transformation is held in a step S76. The steps S72-S76 are repeated until it is decided that all domain blocks in the search range are processed in a step S77. A square error SE smaller than the variable MIN held in the preceding processing cycle is determined and held, and the parameter of the affine transformation is held in the step S76. In this manner, the domain block whose similarity is highest in the search range (with the minimum square error SE) is identified, and the affine transformation parameter is held.
An affine transformation parameter between the range block and the identified domain block whose similarity is highest is coded in a step S78.
The steps S71-S78 are repeated until it is decided that all range blocks in the image to be coded are processed in a step S79, thereby coding an affine transformation parameter between the range blocks and the domain block.
As a result, a domain block whose similarity to each of all the range blocks in the image to be coded is high is identified, and an affine transformation parameter between the range block and the domain block is coded.
According to the above conventional coding processes, however, each time the input block and the search block are changed, or each time the range block and the domain block are changed, it is necessary to calculate a square error SE and an absolute error AE. For calculating a square error SE and an absolute error AE, as many subtractions, multiplications, and additions as the number of pixels contained in blocks have to be repeatedly carried out.
Consequently, as the number of input blocks and search blocks or range blocks and domain blocks increases, the amount of calculations that need to be done also increases, resulting in a slower processing rate. Such a low processing rate presents a large obstacle to efforts to speed up the processing capability of an image data transmission system in particular.